package com.mlh.binarytree;

import java.util.LinkedList;

/**
 * @author 缪林辉
 * @date 2024/8/26 14:32
 * @DESCRIPTION
 */
//给你二叉树的根结点 root ，请你将它展开为一个单链表：
// 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
// 展开后的单链表应该与二叉树 先序遍历 顺序相同。
public class 二叉树展开为链表 {
    //利用先序遍历的迭代法来实现
    public void method1(TreeNode root) {
        if(root==null){
            return;
        }
        LinkedList<TreeNode>stack=new LinkedList<>();
        stack.push(root);
        TreeNode pre=new TreeNode();
        while(!stack.isEmpty()){
            TreeNode pop = stack.pop();
            pre.right=pop;
            if(pop.right!=null){
                stack.push(pop.right);
            }
            if(pop.left!=null){
                stack.push(pop.left);
            }
            pre=pre.right;
            pre.left=null;
        }
    }

    public void practice(TreeNode root) {
        if(root==null){
            return;
        }
        LinkedList<TreeNode>stack=new LinkedList<>();
        stack.addLast(root);
        TreeNode sentry=new TreeNode();
        while(!stack.isEmpty()){
            TreeNode temp=stack.pollLast();
            if(temp.right!=null){
                stack.addLast(temp.right);
            }
            if(temp.left!=null){
                stack.addLast(temp.left);
            }
            sentry.right=temp;
            temp.left=null;
            sentry=sentry.right;
        }
    }
}
